package top.minuy.subject.leetcode.jz_offer_51;

import java.util.Random;
/**
 * @author Minuy
 * @time 18:23
 * @date 2021/8/30
 */
public class _51 {
    static class Solution {
        private int w2(int[] nums) {
            int s = 0;
            int[] temp = new int[nums.length];

            for (int size = 1; size < nums.length; size += size) {
                int l = 0;
                for (int i = l; i + size < nums.length; i = l) {
                    l = i + size + size;
                    if (l > nums.length) {
                        l = nums.length;
                    }
                    s += merge(nums, i, i + size, l, temp);
                }
            }
            return s;
        }

        private int merge(int[] nums, int r, int m, int l, int[] temp) {
            int s = 0;

            for (int i = r; i < l; i++) {
                temp[i] = nums[i];
            }

            int IR = r, IL = m;

            for (int i = r; i < l; i++) {
                if (IR == m) {
                    // s+=(m-IR);

                    nums[i] = temp[IL];
                    IL++;
                } else if (IL == l) {
                    // s+=(IL-m);

                    nums[i] = temp[IR];
                    IR++;
                } else if (temp[IR] <= temp[IL]) {
                    //！！！！！！！！！！！！！！！！！！！！！！！！
                    // 这边这个等于要注意，如果不加等于，则相等的也认为是逆数对
                    // s+=(IL-m);

                    nums[i] = temp[IR];
                    IR++;
                } else {
                    s += (m - IR);

                    // System.out.println("移动交换：val = "+temp[IL]+" index = "+IL);

                    nums[i] = temp[IL];
                    IL++;
                }
            }
            return s;
        }

        private int w1(int[] nums) {
            int result = 0;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i; j < nums.length; j++) {
                    if (nums[i] > nums[j]) {
                        result++;
                    }
                }
            }
            return result;
        }

        public int reversePairs(int[] nums) {
            return w1(nums);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] o = new int[50000];
        int[] o1 = new int[50000];
        Random random = new Random();
        for (int i = 0; i < 50000; i++) {
            o[i] = random.nextInt(50000);
            o1[i] = o[i];
        }

        System.out.println("-> opCount = "+o.length);

//        int[] o = {1,3,2,3,1};
//        int[] o1 = {1,3,2,3,1};

        System.out.println("------merge------");
        long startTime = System.nanoTime();
        System.out.println(solution.w2(o));
        long endTime = System.nanoTime();

        System.out.println("time = " + (endTime - startTime) / 1000000000.0 + " s");

//        for (int i:o) {
//            System.out.print(i+" ");
//        }
//        System.out.println();

        System.out.println("------normal------");
        startTime = System.nanoTime();
        System.out.println(solution.w1(o1));
        endTime = System.nanoTime();

        System.out.println("time = " + (endTime - startTime) / 1000000000.0 + " s");
//        for (int i:o) {
//            System.out.print(i+" ");
//        }
//        System.out.println();
    }
}
